package main

//207. 课程表
func main() {
	numCourses := 2
	pres := [][]int{{1, 0}, {0, 1}}
	can := canFinish(numCourses, pres)
	println(can)
}

func canFinish(numCourses int, prerequisites [][]int) bool {
	// 求拓扑排序，使用深度优先遍历
	preMap := make(map[int][]int, numCourses)
	numStatus := make([]int, numCourses)

	for i := 0; i < numCourses; i++ { // 所有numStatus状态为 0：未搜索、1：一搜索、2：搜索完成
		numStatus[i] = 0
	}

	for _, prev := range prerequisites {
		preMap[prev[0]] = append(preMap[prev[0]], prev[1])
	}

	var checkDfs func(i int) bool
	checkDfs = func(i int) bool {
		if numStatus[i] == 1 {
			return false
		}
		if numStatus[i] == 2 {
			return true
		}
		numStatus[i] = 1
		for _, prev := range preMap[i] {
			ok := checkDfs(prev)
			if !ok {
				return false
			}
		}
		numStatus[i] = 2
		return true
	}

	for i := 0; i < numCourses; i++ {
		ok := checkDfs(i)
		if !ok {
			return false
		}
	}

	return true
}

//207. 课程表
//中等
//相关标签
//相关企业
//提示
//你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
//
//在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。
//
//例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
//请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
//
//示例 1：
//
//输入：numCourses = 2, prerequisites = [[1,0]]
//输出：true
//解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
//示例 2：
//
//输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
//输出：false
//解释：总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
//
//
//提示：
//
//1 <= numCourses <= 2000
//0 <= prerequisites.length <= 5000
//prerequisites[i].length == 2
//0 <= ai, bi < numCourses
//prerequisites[i] 中的所有课程对 互不相同
